/*
练习15-1 分书问题
分数 20
作者 陈越
单位 浙江大学

分书问题是指：已知 n 个人对 m 本书的喜好（n≤m），现要将 m 本书分给 n
个人，每个人只能分到 1 本书，每本书也最多只能分给 1
个人，并且还要求每个人都能分到自己喜欢的书。本题就要求你实现 BookAssignment
函数，用比教材中代码15-4更高效的方法，列出所有满足要求的方案。 函数接口定义：

void BookAssignment( Matrix table, int n, int m );

其中 Matrix 类型的定义如下：

typedef int ElemSet; //  默认矩阵元素为整型
typedef struct MatrixNode *Matrix;
struct MatrixNode {
    ElemSet **t;
    int row;
    int col;
};

函数接口定义中，table 是关系矩阵（table[i][j]=1 表示第 i 个人喜欢第 j
本书，否则取值为 0）；n 和 m 分别为人的数量和书的数量，均为 [2, 8]
区间内的整数。

要求该函数按递增顺序输出所有满足要求的解状态 s，输出时调用裁判给出的函数：

void Print( int *s, int n );

其中 s 是状态向量数组，n 是人的数量。若没有解，则在一行中输出 No Solution。

注意：两组解状态满足 s1​<s2​ 是指，存在下标 0≤k<n 使得
s1​[i]=s2​[i] 对所有 i<k 成立，并且 s1​[k]<s2​[k]。

输入样例：

3 4
0 1 0 1
1 0 1 0
1 1 0 0

输出样例：

(2, 3, 1)
(4, 1, 2)
(4, 3, 1)
(4, 3, 2)
*/

#include <memory.h>
#include <stdio.h>
#include <stdlib.h>

typedef enum { false, true } bool;
typedef int ElemSet; /* 默认矩阵元素为整型 */
typedef struct MatrixNode *Matrix;
struct MatrixNode {
    ElemSet **t;
    int row;
    int col;
};

ElemSet **Create2DArray(int row, int col); /* 动态声明row行col列的二维数组 */
void Free2DArray(ElemSet **t);             /* 释放二维数组空间 */
void Print(int *s, int n);                 /* 输出一组解 */
void BookAssignment(Matrix table, int n, int m);

int main(void) {
    Matrix table;
    int n, m, i, j;

    scanf("%d %d", &n, &m);
    table = (Matrix)malloc(sizeof(struct MatrixNode));
    table->row = n;
    table->col = m;
    table->t = Create2DArray(table->row, table->col);
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            scanf("%d", &table->t[i][j]);
        }
    }
    BookAssignment(table, n, m);
    Free2DArray(table->t);
    free(table);

    return 0;
}

/* 你的代码将被嵌在这里 */

void BookAssignment(Matrix table, int n, int m) {
    int *s = (int *)malloc(sizeof(int) * n); // 分配状态向量数组
    int *book = (int *)malloc(sizeof(int) * m); // 分配书籍标记数组
    memset(book, 0, sizeof(int) * m); // 初始化书籍标记数组为0
    int i = 0, j = 0;
    bool foundSolution = false; // 标记是否找到解

    while (i >= 0) {
        if (i == n) {
            // 如果所有人都分配了书籍，输出解
            Print(s, n);
            foundSolution = true;
            i--;
            if (i >= 0) {
                book[s[i]] = 0; // 回溯，标记书籍未分配
                j = s[i] + 1; // 更新列索引
            }
        } else {
            while (j < m) {
                // 尝试为第i个人分配书籍
                if (table->t[i][j] == 1 && book[j] == 0) {
                    s[i] = j; // 更新状态向量
                    book[j] = 1; // 标记书籍已分配
                    i++;
                    j = 0; // 重置列索引
                    break;
                }
                j++;
            }
            if (j == m) {
                // 如果没有找到合适的书籍，回溯
                i--;
                if (i >= 0) {
                    book[s[i]] = 0; // 回溯，标记书籍未分配
                    j = s[i] + 1; // 更新列索引
                }
            }
        }
    }

    if (!foundSolution) {
        // 如果没有找到任何解，输出 "No Solution"
        printf("No Solution\n");
    }

    free(s); // 释放状态向量数组
    free(book); // 释放书籍标记数组
}